package offer;

@FunctionalInterface
public interface MaximumRequests {
    /**
     *
     * @param n             房间的数量
     * @param requests      换房间请求的数量
     * @return              最大可满足请求数量
     */
    int maximumRequests(int n, int[][] requests);
}
class MaximumRequestsImpl1 implements MaximumRequests{


    /**
     * 原问题可抽象为在一个有向图中不断寻找环，
     * 每一次寻找到一个环，则可以消除这个环意味着相应的换房间请求得到满足，满足了的请求数量n，等于环中边的数量n
     * 重复上述动作直到图中无环，
     * 寻找图中的链，两个以上的请求，构成的边，将它们移位，若链中有n条边，则n-1条边可以消除，即满足n-1个请求
     * 重复上述动作直到图中的边均不相连
     * 上述过程中消除的边的数量就是最大可满足请求的数量
     * @param n             房间的数量
     * @param requests      换房间请求的数量
     * @return              最大可满足请求数量
     */
    @Override
    public int maximumRequests(int n, int[][] requests) {
        return 0;
    }
    int[][] map;
}
